package com.leo.leetcode.s100;

/**
 *
 * @author xuexiaolei
 * @version 2017年11月16日
 */
public class T05LongestPalindromicSubstring {
    public static String longestPalindrome(String s) {
        if (s == null || "".equals(s)) return "";
        char[] chars = s.toCharArray();
        int ansStart=0,ansEnd=0;
        int start=0,end=0;
        char[] stack = new char[s.length()];//模拟栈
        int pos=0;//当前栈的位置

        for (int i = 0; i < s.length(); i++) {
            //入栈
            stack[pos] = chars[i];
            pos++;
            //判断栈
            if ((pos-2>=0) && (stack[pos-1]==stack[pos-2])){
                start = pos-2;
                end = pos -1;
                pos = pos-2;
                if ((end-start) > (ansEnd-ansStart)){ ansEnd=end; ansStart=start; }
            }
        }
        pos=0;
        start=0;
        end=0;
        for (int i = 0; i < s.length(); i++) {
            //入栈
            stack[pos] = chars[i];
            pos++;
            //判断栈，中间可以加单个字符的情况
            if ((start == end) && (pos-3>=0) && (stack[pos-1]==stack[pos-3])){
                start = pos-3;
                end = pos -1;
                pos = pos-3;
                if ((end-start) > (ansEnd-ansStart)){ ansEnd=end; ansStart=start; }
            }
        }



        StringBuffer sb = new StringBuffer();
        for (int i = ansStart; i <= ansEnd ; i++) {
            sb.append(chars[i]);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("babad"));
        System.out.println(longestPalindrome("cbbd"));
        System.out.println(longestPalindrome("a"));
        System.out.println(longestPalindrome("aba"));
        System.out.println(longestPalindrome(""));
        System.out.println(longestPalindrome("ccc"));
        System.out.println(longestPalindrome("cccc"));//无法解决问题
    }
}
